// Segundo trabalho de Programacao Concorrente
// Deteccao de Palindromos
// Daniel Hatanaka, 7277579
// Guilherme Kalatzis, 7239426
// Thiago Tanaka, 7153014
// Prof. Dr. Julio Estrella, Estagiario PAE Luiz Henrique Nunes

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<mpi.h>

// Conjunto de caracteres que nao farao parte de palavras e frases, para que palindromos possam ser verificados
char ignoreList[45] = {EOF, '.', '\r', '\n', ' ', '(', ')', '-', '1', '2',
						'3', '4', '5', '6', '7', '8', '9', '0', '\'', ':',
						'\t', ',', ';', '!', '?', 9, '[', ']', '|', '&',
						'/', '\\', '*', '"', '+', '$', '@', '%', '<', '>',
						'^', '_', '~', '#', '='};
// Serao calculados os numeros primos ate um milhao
unsigned int primes[1000000];

// Algoritmo do crivo de Eratostenes
void sieveOfEratosthenes() {
	long long int i, j;
	// 0 e 1 nao sao considerados primos, 2 sim
	primes[0] = 0;
	primes[1] = 0;
	primes[2] = 1;
	// Todos os numeros pares nao sao primos e impares sao candidatos
	for(i = 3; i < 1000000; i++)
		primes[i] = i % 2;

	// For somente ate a raiz de um milhao, anda somente pelos impares
	for(i = 3; i*i < 1000000; i += 2)
		if(primes[i])
			// Eh garantido que de i*i para tras, todos os primos ja foram marcados
			// O for anda por todos os multiplos de i
			for(j = i*i; j < 100000; j += i)
				// Nao eh primo pois eh multiplo de i
				primes[j] = 0;
}

// Checa se uma string (passada por parametro) eh um palindromo
// Retorna 1 se verdadeiro e 0 caso contrario
int checkPalindrome(char *string) {
	// Utiliza dois marcadores, um no inicio e outro no final da string
	int begin = 0, end = strlen(string)-1;
	// Nao considera strings com um unico caractere como palindromos
	if (strlen(string) <= 1)
		return 0;
	// Enquanto os marcadores nao se cruzarem
	while (begin < end)
		// Percorre a string em sentido opostos comparando caracteres equidistantes, se forem diferentes nao eh um palindromo
		if(string[begin++] != string[end--])
			return 0;
	// Caso nenhum dos caracteres forem diferentes, a funcao nao tera retornado e a string entao eh um palindromo
	return 1;
}

// Conta numero de palavras palindromas e numero de somas ASCII primas dos palindromos dentro de uma parte do arquivo de entrada (a entrada eh dividida para as threads)
// palindromeCount e primeCount sao parametros passados por referencia, portanto mantem seus conteudos apos a chamada desta funcao
void countPalindromeWordsInPart(char *part, int *palindromeCount, int *primeCount) {
	int palindromeLocalCount = 0, primeLocalCount = 0;
	char character, word[10000];
    long i, j, partLength = strlen(part), index = 0, wordSum;
	// Percorre todos os caracteres da parte da entrada
	for (i = 0; i < partLength; i++) {
		character = part[i];
		if(character == ' ' || character == '.' || character == ',' || character == '\r' || character == 9) {
			// Finaliza a palavra pois achou marcador final de palavra
			word[index] = '\0';
			// Verifica palindromo de palavra
			if(checkPalindrome(word)) {
				palindromeLocalCount++;
				wordSum = 0;
				// Realiza soma dos valores ASCII da palavra
				for(j = 0; j < strlen(word); j++)
					wordSum += word[j];
				// Verifica se eh primo e atualiza contador de primos
				if(primes[wordSum])
					primeLocalCount++;
			}
			index = 0;
		}
		// A funcao strchr checa se existe a ocorrencia de um caractere em uma string - retorna o ponteiro da primeira ocorrencia
		// Logo, se o caractere nao esta contido na lista de ignorados, ele pode ser adicionado a palavra
		if (strchr(ignoreList, character) == NULL) {
			// Transforma as letras em minusculas
			if (character >= 'A' && character <= 'Z')
				character += 'a' - 'A';
			// Adiciona o caractere a palavra
			word[index++] = character;
		}
	}
	// O for terminara quando a entrada acabar, porem a ultima palavra tem que ser finalizada para nao ser perdida
	word[index] = '\0';
	// Verifica palindromos
	if(checkPalindrome(word)) {
		palindromeLocalCount++;
		wordSum = 0;
		// Realiza soma dos valores ASCII da palavra
		for(j = 0; j < strlen(word); j++)
			wordSum += word[j];
		// Verifica se eh primo e atualiza contador de primos
		if(primes[wordSum])
			primeLocalCount++;
	}
	// Atualiza parametros passados por referencia para que possam ser utilizados fora da funcao
	*palindromeCount = palindromeLocalCount;
	*primeCount = primeLocalCount;
}


int main(int argc, char* argv[]) {
    double startingTime = 0, endingTime = 0, totalTime = 0, auxTime = 0;
    int i, palindromeWordCount = 0, numPrimes = 0;
	FILE *file;
	char *fileBuffer;
	int verify, size,rank, aux;
	MPI_Status status;
    long fileSize, index, previousIndex;

    // Inicia um processo MPI
    verify = MPI_Init(&argc, &argv);
    // Verifica se foi criado com sucesso
    if(verify != MPI_SUCCESS){
        printf("Erro...\n");
        exit(1);
    }
    // Salva em RANK o numero do processo criado
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    // Salva em SIZE o numero de processos a serem criados
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    // Marca o tempo inicial da execucao
    startingTime = MPI_Wtime();

    char *parts[size];

    // Chama o crivo
    sieveOfEratosthenes();

    // Primeiro  nó executado que é responsável por gerenciar os outros nós
    if(rank == 0){
        puts("\nArquivo maior (wikipedia.txt):");
        // Abre o arquivo com o modificador "r", que eh de leitura
        file = fopen("data/wikipedia.txt", "r");
        if (file == NULL) {
            puts("Erro ao abrir o arquivo:");
            perror("data/wikipedia.txt");
        } else {
            // Move o cursor para o fim do arquivo
            fseek(file, 0, SEEK_END);
            // Descobre o tamanho do arquivo
            fileSize = ftell(file);
            // Volta o cursor para o comeco
            fseek(file, 0, SEEK_SET);
            // Aloca memoria para o buffer
            fileBuffer = (char *)calloc(sizeof(char), fileSize);
            // Le o arquivo inteiro e passa o conteudo para o vetor alocado
            fread(fileBuffer, sizeof(char), fileSize, file);

            previousIndex = 0;
            // Variavel para indicar tamanho da parte a ser enviada
            long tamEnvio=0;
            // Divide o conteudo do arquivo em varias partes (de acordo com o numero de processos a ser utilizado)
            for(i = 0; i < size-1; i++) {
                // Coloca um marcador na posicao final da parte a ser coletada
                index = (i + 1) * fileSize / (size-1);
				// Procura por um ponto ou espaco proximo, para palavras nao ficarem incompletas
				while (index != strlen(fileBuffer) && fileBuffer[index] != '.' && fileBuffer[index] != ' ')
					index++;
                // Aloca a memoria para a parte do arquivo de entrada
				parts[i] = (char *)calloc(sizeof(char), index - previousIndex);
				// Atualiza o tamanho da parte a ser enviada
				tamEnvio = index - previousIndex;
                // Copia o trecho do buffer para o vetor alocado
				strncpy(parts[i], fileBuffer + previousIndex, index - previousIndex);
				// Atualiza o marcador de comeco da parte
				previousIndex = index;
				// Envia o valor do tamanho da parte para cada processo
				MPI_Send(&tamEnvio, 1, MPI_LONG, i+1, 4, MPI_COMM_WORLD);
                // Envia a parte do arquivo para cada processo
				MPI_Send(parts[i], tamEnvio, MPI_CHAR, i+1, 1, MPI_COMM_WORLD);
			}
			// Desaloca as partes auxiliares que foram enviadas
			for (i = 0; i < size-1; i++){
                free(parts[i]);
            }
			for (i = 1; i < size; i++) {
                // Recebe o valor calculado de cada palíndromo dos outros processos
                MPI_Recv(&aux, 1, MPI_INT, i, 2, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				// Atualiza a contagem global dos palíndromos totais
				palindromeWordCount += aux;
				// Recebe o valor calculado dos primos de cada processo
				MPI_Recv(&aux, 1, MPI_INT, i, 3, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				// Atualiza a contagem global dos primos
				numPrimes += aux;
				// Recebe o tempo de execução de cada processo
                MPI_Recv(&auxTime, 1, MPI_DOUBLE, i, 5, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                // Atualiza o tempo total de cada processo
				totalTime += auxTime;
            }
            // Fecha o arquivo aberto
            fclose(file);
        }
        // Imprime os resultados
        printf("Por palavras: %d palindromos\n", palindromeWordCount);
        printf("Numero de somas ASCII primas: %d palindromos\n", numPrimes);
        printf("Tempo: %.2lfs\n\n", totalTime);
        // Desaloca o buffer
        free(fileBuffer);
    }
    // Nós "filhos" para processamento de cada parte do arquivo
    else{
        long tamEnvio=0;
		char *bloco;
        int auxWord=0, auxPrime=0;

        // Recebe o tamanho do bloco do arquivo a ser alocado
        MPI_Recv(&tamEnvio, 1, MPI_LONG, 0, 4, MPI_COMM_WORLD, &status);
        // Aloca o bloco para receber a parte do arquivo
        bloco = (char *)malloc(tamEnvio*sizeof(char));
        // Recebe a parte do arquivo a ser processada
        MPI_Recv(bloco, tamEnvio, MPI_CHAR, 0, 1, MPI_COMM_WORLD, &status);
        // Chama a funcao que conta palindromos na parte, os ints de contadores sao passados por referencia, entao podem ser utilizados posteriormente
        countPalindromeWordsInPart(bloco, &auxWord, &auxPrime);
        // Envia pro nó 0 (zero) o valor calculado dos palíndromos
        MPI_Send(&auxWord, 1, MPI_INT, 0, 2, MPI_COMM_WORLD);
        // Envia para o nó 0 (zero) o valor calculado dos primos
        MPI_Send(&auxPrime, 1, MPI_INT, 0, 3, MPI_COMM_WORLD);

        // Calcula o tempo final
        endingTime = MPI_Wtime();
        totalTime = endingTime - startingTime;
        // Envia para o nó gerenciador, 0 (zero), o tempo total de execução do filho
        MPI_Send(&totalTime, 1, MPI_DOUBLE, 0, 5, MPI_COMM_WORLD);
    }
    // Finaliza a execução em paralelo MPI
    MPI_Finalize();
    return 0;
}
